/*
 * @lc app=leetcode.cn id=78 lang=javascript
 *
 * [78] 子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */

// // 子集问题，
// // 用二进制第i位是否为1表示第nums第i个数是否选择
// var subsets = function(nums) {
//   const n = nums.length;
//   let ret = [];

//   // n个1的二进制
//   for (let i = 0; i <= (1 << n) - 1; i++) {
//     let temp = []

//     // 遍历二进制的i的每一位
//     for (let j = 0; j < n; j++) {
//       // i的二进制每一位即表示nums对应位是否选择
//       // 判断i的第j位是否为1 
//       if((i >> j) & 1){
//         temp.push(nums[j])
//       }
//     }
//     ret.push(temp);
//   }

//   return ret;
// };


var subsets = function(nums) {
  // 根据数值，求出是2的几次方
  let map = {};
  for (let i = 0, j = 1; i < 10; i++, j <<= 1) map[j] = i; 

  let n = nums.length;
  let ret = [];

  for (let i = 0; i < (1 << n); i++) {
    let temp = [];
    let val = i;
    while(val) {
      // val & (-val) 得出val的二进制最后一个1
      // val & (val - 1) 涮出最后一个1 
      
      let power = map[val & (-val)]; // 2的几次幂
      temp.push(nums[power]);
      val = val & (val - 1);
    }
    ret.push(temp);
  }
  return ret;
}
// @lc code=end

